package pl.mmadej.ds4java.ds.heap;


import pl.mmadej.ds4java.ds.array.ArrayDecorator;
import pl.mmadej.ds4java.ds.common.DataStructure;

public class ArrayMaxHeap<T extends Comparable<T>> extends DataStructure<T> implements MaxHeap<T> {

    private int size;
    //cannot inherit because of quick sort
    private ArrayDecorator<T> array;

    public ArrayMaxHeap(int size) {
        array = new ArrayDecorator<T>(size);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void insert(T element) {
        assertNotNull(element);
        array.setAt(size++, element);
        maxHeapifyUpElementAt(size - 1);
    }

    @Override
    public void remove(T element) {
        int indexOfElement = indexOf(element);
        if (indexOfElement != -1) {
            removeElementAt(indexOfElement);
        }
    }

    private int indexOf(T element) {
        for (int index = 0; index < size; index++) {
            if (array.elementAt(index).equals(element)) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public T max() {
        return array.elementAt(0);
    }

    @Override
    public T popMax() {
        T elementToReturn = null;
        if (size != 0) {
            elementToReturn = array.elementAt(0);
            removeElementAt(0);
        }
        return elementToReturn;
    }

    @Override
    public void clear() {
        array.clear();
        size = 0;
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    private void maxHeapifyDownElementAt(int index) {
        int largestChildElementIndex = largestChildIndex(index);
        while (isInArrayBounds(index) && swapRequiredForElementsAt(largestChildElementIndex, index)) {
            array.swapElementsAt(largestChildElementIndex, index);
            index = largestChildElementIndex;
            largestChildElementIndex = largestChildIndex(index);
        }
    }

    private int largestChildIndex(int index) {
        int indexToReturn = index;
        int leftChildIndex = leftChildIndexForElementAt(index);
        int rightChildIndex = rightChildIndexForElementAt(index);
        if (leftChildIndex < size && rightChildIndex < size) {
            indexToReturn = indexForLargestElementFromTwoAt(leftChildIndex, rightChildIndex);
        } else if (leftChildIndex < size) {
            indexToReturn = leftChildIndex;
        }
        return indexToReturn;
    }

    private void removeElementAt(int indexOfElement) {
        array.setAt(indexOfElement, array.elementAt(--size));
        array.setAt(size, null);
        maxHeapifyDownElementAt(indexOfElement);
    }

    private int indexForLargestElementFromTwoAt(int leftChildIndex, int rightChildIndex) {
        T leftElement = array.elementAt(leftChildIndex);
        T rightElement = array.elementAt(rightChildIndex);
        return rightElement.compareTo(leftElement) > 0 ? rightChildIndex : leftChildIndex;
    }

    private void maxHeapifyUpElementAt(int index) {
        int parentIndexForElement = parentIndexForElementAt(index);
        while (isInArrayBounds(parentIndexForElement) && swapRequiredForElementsAt(index, parentIndexForElement)) {
            array.swapElementsAt(index, parentIndexForElement);
            index = parentIndexForElement;
            parentIndexForElement = parentIndexForElementAt(parentIndexForElement);
        }
    }

    private boolean swapRequiredForElementsAt(int index, int parentIndexForElement) {
        T parentElement = array.elementAt(parentIndexForElement);
        return array.elementAt(index).compareTo(parentElement) > 0;
    }

    private boolean isInArrayBounds(int parentIndexForElement) {
        return parentIndexForElement >= 0 && parentIndexForElement < size;
    }

    private int parentIndexForElementAt(int index) {
        return (index + 1) / 2 - 1;
    }

    private int leftChildIndexForElementAt(int index) {
        return 2 * (index + 1) - 1;
    }

    private int rightChildIndexForElementAt(int index) {
        return 2 * (index + 1);
    }
}
